//
// Description: 77. 组合
// Created by Loading on 2025/5/28.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> res;

    function<void(int, vector<int> &)> backtrace = [&](int index, vector<int> &v) {
        if (v.size() == k) {
            res.emplace_back(v);
        } else {
            for (int i = index; i <= n; ++i) {
                if (v.size() + n - index + 1 < k) { // 剩余数据不足，剪枝
                    return;
                }
                v.emplace_back(i); // 选择当前位置
                backtrace(i + 1, v);
                v.pop_back(); // 不选择当前位置
            }
        }
    };

    vector<int> v;
    backtrace(1, v);

    return res;
}

int main() {
    int n = 6;
    int k = 3;

    auto res = combine(n, k);

    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}
